﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace HeapPermute
{
    class Program
    {
        #region INFO
        //http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

        #endregion

        public int? Count { get; set; }
        public object CountLock { get; set; }
        private object[] array = { "A", "B", "C", "D" };


        private void Run()
        {
            Count = 0; this.CountLock = new Object();
            HeapPermute(4);
            Console.WriteLine("Count: " + Count);
            Console.ReadLine();
        }


        void HeapPermute(int n)
        {
            if (n == 1)
            {
                PrintItem();
            }
            else
            {
                //for (int j = 0; j < n; j++)
                //{
                    for (int i = 0; i < n; i++)
                    {
                        HeapPermute(n - 1);
                        if (n % 2 == 1)  // if n is odd
                            swap(0, n - 1);
                        else            // if n is even
                            swap(i, n - 1);
                    }
                //}
            }
        }


        void PrintItem()
        {
            Console.WriteLine(String.Join(",", array.Select(p => p.ToString()).ToArray()));

            lock (CountLock)
            {
                Count++;
            }
        }


        void swap(int i, int j)
        {
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

    }
}
